\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{wrapfig}



\usepackage[francais]{babel}

%opening
\title{Rapport du projet de sémantique et traduction des langages \\%
Compilateur Micro Objective C \\%
\textbf{Première partie : Micro C }}
\author{Victor Proto \\% 
Fabien Sauce \\% 
Fourat Ferchichi}

\begin{document}

\maketitle
\clearpage
\tableofcontents

\clearpage
\section{Introduction}

Le but de cette première partie du projet, outre que d'en amorcer 
la seconde, est de concevoir et d'implémenter
avec les outils mis à disposition un compilateur du langage Micro C,
qui n'est autre qu'un sous ensemble du langage 
C.\\%
La grammaire fournie pour cette partie comprend les types de base (mais vraiment de base), les opérations arithmétiques
et logiques élémentaires (bien que le type booléen n'existe pas, on s'en sort quand même) et les incontournables définitions
et appels des fonctions (même récursives, la chance !)  \\%

Les outils utilisés sont :
\begin{itemize}



\item Le générateur de compilateur EGG, dans sa version Plugin Eclipse 
\item L'outil itam qui marche une fois sur dix en Plugin Eclipse, nous avons donc préféré utliser la version ``logiciel normal''
\item Un répertoire SVN \url{https://code.google.com/p/compilo/} pour synchroniser l'avancement du projet, surtout qu'il s'est fait 
en période pascale.

\end{itemize}


La répartition des tâches est d'autant plus classique que le travail 

On s'est permis d'ajouter quelques extensions à la grammaire, sans que celà ne la modifie bien sûr, 
L'instruction Tant que \textbf{While}, sans laquelle on ne dispose que de la récursivité pour calculer la factorielle 
(un peu gênant quand même)
L'instruction allocation mémoire \textbf{new Type()}, car on a estimé que c'est un peu lourd de la redéfinir à chaque fois qu'on voulait
l'utiliser dans un fichier.
\clearpage
\section{Conception}

\subsection{Système de types}
\subsubsection{Généralités}
Chaque type a eu droit à sa classe JAVA.
Pour tester la compatibilité entre deux types on a eu recours à deux méthodes d1ifférentes 
\begin{itemize}
\item \textbf{equals} : qui teste l'égalité exacte entre deux types 
\item \textbf{conforms} : qui teste la compatiblité, et dont on a besoin dans le cas du cast 
\end{itemize}

Dans un soucis de rigueur, dans les types de base, on a préféré distinguer entre deux catégories 
\begin{itemize}
\item Les types ``rangés'' \textbf{ROWTYPE} :
qui sont les entiers et les caractères,
et sur lesquels
les opérations arithmétiques peuvent 
s'effectuer naturellement(sous condition 
d'appartenance au domaine du type bien sûr \textbf{cf.}implémentation) 

\item Les autres types : dans notre cas c'est l'unique type pointeur, quoique, 
il est bien possible que ce type appartienne
à la catégorie des rangés, et celà implique que le futur 
développeur devra maîtiser l'arithmétique des pointeurs...

\end{itemize} 

Le cas du \textbf{NULL} 
La littérature (Wikipédia...) dit que null est une variable d'état du type pointeur 
nous avons donc été tenté au début de créer un attribut booleen etat dans la classe POINTEURTYPE qui indique cet état 
Mais ce choix a posé un grand problème quand il a fallu l'implémenter sémantiquement,
en effet les cas où cet état est suceptible 
de changer sont imprévisibles (exemple : une fonction qui renvoie un pointeur...) 
On a donc créer une classe NULL qui hérite de DTYPE (même si ce n'est pas un type) 

\subsubsection{Egalité et conformité}
\begin{quote}
 C'est votre compilateur, vous en faites ce que vous voulez 
\end{quote}


Sans Cast, seule l'égalité entre les types est vérifiée.
\paragraph{Les entiers}
Les entiers sont conformes aux 
\begin{itemize}
 \item aux entiers bien évidemment
 \item aux caractères, si on respecte le domaine ASCII 
 \item aux pointeurs 
\end{itemize}

\paragraph{Les caractères}
Les caractères sont conformes aux 
\begin{itemize}
 \item aux caractères bien évidemment
 \item aux entiers
\end{itemize}

\paragraph{Les pointeurs}
Les pointeurs sont conformes aux 
\begin{itemize}
 \item pointeurs sous conditions ques les types pointés sont `\textbf{egaux} (et non conformes) 
 \item aux entiers
 \item aux tableaux, à condition que le type du tableau soit \textbf{égal} au type pointé 
\end{itemize}

\paragraph{Le type vide}
Deux choix se sont présentés quant à ce type
\begin{itemize}
 \item Il n'est conforme à rien, ce qui évite beaucoup de problèmes.
 \item Il est conforme à tout,on pourrait alors l'utiliser pour implémenter le type abstrait \verb|void * |
qui est utilisé dans le vrai C pour indiquer par exemple qu'une fonction renvoie un pointeur sans se soucier du type 
pointé par ce dernier :\verb|void *malloc(size_t size);| \\%
Mais l'un des inconvénients de ce choix est le fait de pouvoir affecter un void à un int par exemple
\end{itemize}

Finalement le second choix a été adopté mais avec une petite nuance: \verb|void| est conforme à tout et égal à lui même seulement.

 

\subsection{Les fonctions}
Une fonction est caractérisée par son identifiant, et sa signature, une signature étant la liste ordonée des types 
des paramètres, et son type de retour.

\subsection{La fameuse (ou pas) table des symboles}
\subsubsection{Généralités}
Les entités du programme se partagent une même table des symboles.et chaque fonction a une table des symboles, fille de la principale
La table des symboles de chaque fonction contient : 
\begin{itemize}
 \item Une Information sur la fonction elle même 
 \item Les paramètres sous forme de variables dont les adresses sont stockées négativement par rapport à \verb|0[LB]|
\end{itemize}


\subsubsection{Méthodes de recherche et prise en compte de la surcharge}
\paragraph{La surcharge}
La surcharge porte exclusivement sur \textbf{la signature}, on ne peut pas définir deux méthodes avec des types de retour 
différents et des signatures identiques,
car lors de l'appel d'une fonction, rien ne suggère au compilateur quel est le type de retour attendu.(cf.implémentation)
\paragraph{Adaptation de la table des symboles à la surcharge}
Pour prendre en compte la surcharge, les méthodes de la table des symboles ne se limitent pas au critère
de l'égalité entre identifiants.On a donc muni notre table de deux fonctions de recherche pour les fonctions



\clearpage
\section{Implementation}
Afin que ce rapport soit concis et précis (comme le veut la tradition), nous n'allons détailler que l'implémentation
des règles de production qui nous ont semblées les plus délicates à traiter (les nouveautés par rapport au langage BLOC en 
l'occurence).
\subsection{Les types}
\subsubsection{Types de base : Entiers, Caractères, et Vide}
RAS
\subsubsection{Le type Pointeur}

\verb|int **| \\%
bleu pour les attributs synthétisés et rouge pour les attributs hérités 

\includegraphics{./arbre32.png}


\subsubsection{Les tableaux}
L'implémentation du type tableau s'est faite à l'aide de la nouvelle règle : \\%
\verb|REFS -> cro entier crf crf REFS| \\%
Ce qui permet entre autres de déclarer un tableau à plusieurs dimensions (même si le traitement dans notre compilateur 
se limite à une seule dimension) un pointeur sur un tableau ou un tableau de pointeurs.
La construction du type se fait de manière identique à celle du type pointeur.\\%
L'exemple suivant illustre comment construire 
un pointeur sur un tableau


\verb|int[5]*;|



 \includegraphics{./arbre6.png}\\%




Le type Tableau implémenté est un peu limité : 
c'est un tableau à une dimension, bien que selin la grammaire, on peut déclarer plusieurs dimensions
la taille déclarée ne peut être que sous la forme d'un entier, faute de quoi, on ne peut instancier le type tableau : 
si la taille était sous forme d'une expression ou d'un identifiant, il nous fallait une allocation dynamique 
...

A noter que notre compilateur ne fait pas la différence entre un tableau proprement dit et un pointeur sur un tableau, vu 
que  la manipulation des deux types *type[] et type[] revient à un calcul d'adresses, à des enregistrements des chargements indirects
Notre compilateur, comme beaucoup d'autres, ne contrôle malhereusement pas les débordement d'indices, c'est au développeur 
de faire attention à ce qu'il écrit...
\subsection{Les expressions arithmétiques et logiques}
\subsubsection{Le contôle de types}
\textbf{AUCUN MÉLANGE DE TYPES N'EST AUTORISÉ DANS LES EXPRESSIONS, } (à moins d'utiliser un cast...) \\%




\subsubsection{Un mot sur la génération de code pour les expressions}


\subsection{Les structures de contrôle}
\subsubsection{Structure de contrôle}
\subsection{La déclaration et l'affectation}

\verb| INST ->  TYPE ident  AFFX pv  ;|

La partie déclaration ne présente rien de nouveau, il suffit de :
\begin{itemize}
\item Vérifier que l'identifiant n'a pas été déjà utilisé dans le bloc courant 
\item Ajouter une nouvelle variable à la table des symboles courante
\item Augmenter le déplacement de l'instruction 
\item Le code de l'instruction est le code de \verb|AFFX |
\end{itemize}

Reste maintenant à gérer le code du \verb|AFFX |, qui est présent dans une autre règle de production, 
celle de l'affectation sans déclaration : 
\verb|E ->  A  AFFX ; |

Par conséquent, il faut distinguer deux cas :
\begin{itemize}
\item Le cas ou l'\verb|AFFX| est dans l'instruction déclarative 
\item Le cas où  l'\verb|AFFX| est dans l'instruction d'affectation sans déclaration 
\end{itemize}
D'où l'attribut hérité decl pour \verb|AFFX|, de type booléen qui permet de faire cette distinction lors de la génération 
du code.
Concrètement, on a besoin de cet attribut lorsque il y a déclaration simple sans affectation, dans ce cas, il faut 
réserver l'espace dans la pile pour la variable qui vient d'être déclarée
Explication 
\verb|AFFX ->  ; |
si \verb|AFFX| est appelé lors d'une déclaration, le code sera une réservation mémoire (ie un PUSH de la taille du type de 
la variable), sinon AFFX n'aura pas de code 


\subsubsection{Contrôle de l'affectabilité}
Il est clair que les instructions \verb|2 = 5 ;| et \verb|2+5 = 'c'| ne sont pas possibles 
donc il faut contrôler que la partie gauche de la règle \verb|A AFFX ;|  est affectable 

On a eu donc recours à un un attribut synthétisé \verb|syn isAFF : boolean for F,R,T,A,AX,TX,RX ;| (pour isAffectable) qui se transmet de F à T à R et enfin A 
Les cas où \verb|F^isAff| est initialisé à vrai sont
\begin{itemize}
 \item identifiant (pourvu qu'il soit d'une variable et pas d'une fonction) 
 \item accès à un élément d'un tableau 
 \item accès au contenu d'un pointeur 
\end{itemize}

Concernant les suffixes \verb|AX,TX,RX |, l'attribut est vrai quand ils sont vides (une expression n'est pas affectable bien sûr) 


Pour les autres cas (entier, caractère, chaîne de caractères, appel de fonction) cet attribut est initialisé à faux.
Enfin un attribut hérité hisAff pour AFFX reçoit 
\begin{itemize}
 \item \verb|A^isAff| pour la règle \verb|E -> A AFFX ;|
 \item Vrai pour la règle \verb|INST -> TYPE ident AFFX ; |
\end{itemize}

et le contrôle se fait dans la règle  \verb|AFFX -> affect A ;|
dans le cas où \verb|AFFX^hisAff| est faux, une erreur est déclenchée.\\%

\textbf{Des arbres décorés pour illustrer :} \\% 
\textbf{Exemple 1 :}\\%
\verb|2 = 5 ;|


\includegraphics{./arbre1.png}\\%


\textbf{Exemple 2 :}\\%
\fbox{\verb|i +1  = 5 ;|}\\%

\includegraphics{./arbre2.png}\\%

\subsubsection{Gauche, Droite (aucune arrière-pensée politique...)}
Le code est généré pour une expression en fonction qu'elle soit ``affecté'' ou ``affectable''.\\%
on dispose des règles : 
\begin{itemize}
 \item \verb|E -> A AFFX ;|  \textbf{(1)}
 \item \verb|AFFX -> affect A ;| \textbf{(2)}
\end{itemize}


Le code généré pour le \verb|A| dans \textbf{(1)}est un enregistrement (\verb|STORE| ou \verb|STOREI|)  dans le contenu de A
tandis que dans \textbf{(2)} c'est juste un chargement 
du contenu de A (\verb|STORE| ou \verb|STOREI|). \\%
On a donc utilisé un attribut hérité ``gauche'' de type booléen pour E et compagnie (A,R,T,F) pour indiquer la position de l'expression 
par rapport à l'\textsl{affect} .
\begin{itemize}
\item dans le cas (2)  \verb|A^gauche| a naturellement la valeur \verb|false|
\item dans le cas (1), tout dépend de E, car si E est juste une expression logique, il n'y a pas d'affectation et la valeur 
doit être mise à \verb|false| donc \verb|A^gauche := E^gauche| et \verb|E^gauche| est mise à la valeur \verb|true| uniquement 
dans la règle de production \verb|INST -> E pv ;| car is s'agit là de l'affectation 
\end{itemize}
.
\textbf{Exemples}\\%
\begin{itemize}
 \item \verb|i = 2 ;| \\%

 \fbox{\includegraphics{./arbre4.png}
}


\item \verb|if (i==j) {}| \\%

 \fbox{\includegraphics{./arbre5.png}}


\end{itemize}






\subsection{Les fonctions}

\subsubsection{La définition d'une fonction}

Après avoir vérifié qu'une fonction avec un même identifiant n'a pas été déclaré avant on procède comme suit :

\begin{itemize}
 \item \textbf{Construction de la liste des paramètres : La signature}\\%
 Pour ce faire on dispose de la classe \verb|SIGNATURE| qui hérite de \verb|HashMap<String,DTYPE>| dans la quelle 
 on stocke les identifiants avec leurs types\\%
 \textbf{Remarque} : la classe \verb|SIGNATURE|  hérite de \verb|java.util.LinkedHashMap|, qui contrairement à sa classe mère 
  \verb|java.util.HashMap|, garantit l'ordre avec lequel on y a mis les éléments. Le seul inconvénient est qu'elle peut contenir 
  des clés dubliquées, d'où il fallait contôler que l'identifiant d'un paramètre n'a pas été utilisé avant.\\%
 \textbf{Exemple}
 La fonction \verb|int foo (int a, int b, char* c)| \\%

\clearpage
\begin{figure}
\hspace{-3cm}
 \fbox{\includegraphics{./arbre8.png}}
 
\end{figure}
\item \textbf{Le type de retour} \\%
Le type de retour est extrait est hérité ensuite par toutes les instructions et ceci pour plusieurs raisons
\begin{itemize}
 \item Le contrôle de type de l'expression à retourner quand on rencontre l'instruction de retour. 
 \item Si le type est \verb|void| et qu'on rencontre une instruction de retour, on déclenche une erreur. 
 \item Si le type est \verb|void|, le code généré pour la fonction est la concaténation du code du BLOC et du code d'un 
 retour artificiel qui permet uniquement le dépilement des arguments empilés lors de l'appel de la fonction.
\end{itemize}
\item \textbf{L'instruction de retour} \\%
Il faut vérifier après l'analyse de la totalité du corps de la fonction que si son type est différent de \verb|void|, elle 
contient au moins un instruction de retour, c'est l'objectif de l'attribut synthétisé \verb|ret| de type booléen 
qui indique s'il y a eu une telle instruction ou pas.\\%
Cet attribut a son équivalent \verb|ret_asm| du côté de la grammaire de TAM, qui se calcule de la même manière au cas 
ou l'instruction de retour serait directement mise inline.
\item \textbf{La taille des arguments} \\%
La somme des tailles des arguments est calculèe parallèlement au calcul des leurs déplacements, elle est esuite transmise à
l'ensemble des instructions de la fonction afin de paramétrer l'instruction de retour.
\item \textbf{La table des symboles de la fonction}\\%
La table des symboles de la fonction contient : 
\begin{itemize}
 \item La fonction elle même pour assurer la récursivité.
 \item les paramètres de la fonction, qui sont considérés comme des variables, mais dont les adresses ont été calculées lors
 de la construction de la signature.\\%
 Le calcul des adresses se fait négativement. Il est similaire au calcul des déplacements en remplaçant 
 les additions par des soustractions.
\end{itemize}

\end{itemize}






\subsubsection{L'appel de fonction }
\verb|F ->  ident paro ARGS parf|
Les vérifications à faire avant la génération du code sont
\begin{itemize}
 \item vérifier que l'identifiant est dans la table des symboles et qu'il correspond à une fonction.
 \item Vérifier que la liste des arguments passés est conforme à la signature de la fonction déclarée 
\end{itemize}
\paragraph{Construction de la liste des arguments} 
Un arbre décoré pour illustrer.\\%
soit la liste des arguments \verb | (5, 6,'m') |\\%
\paragraph{Limites}
S'il y a appel de fonctions imbriquées et qu'elles se partagent des paramètres (\verb|foo(boo(a),a)|) 
il y a un risque d'erreur si la fonction intérieure change la valeur du paramètre partagée et ceci est dû que l'empilement 
du paramètre se fait avant l'exécution de la fonction intérieure. 


\includegraphics{./arbre71.png}
Bien évidemment, la construction de la liste des arguments est accompagnée par l'emplilement  de leurs codes.\\%
Le type de F est le type de retour de la fonction.
\clearpage
\section{Divers}
\subsection{Les expressions sans affectation}
La grammaire autorise les instructions du type 
\begin{itemize}
 \item \verb| 5 ;|
  \item \verb| a ;|
   \item \verb| foo(x,y) ;| (foo retourne un entier) 
\end{itemize}


Mise à part les procédures (les fonctions de type \verb|void| ces instructions perturbent
complètement l'adressage étant donné que dans la règle \verb|INST -> E pv ; | le déplacement ne change pas
car elle traduit l'affectation.
Pour palier à ce problème on a créé un attribut booléen \verb|existe| qui indique si il y a affectation ou non.
\begin{itemize}
 \item S'il y a affectation (\verb|AFFX -> affect A ;| ) alors le déplacement ne change pas
 \item Sinon, le déplacement est augmenté de la taille du type de E.
\end{itemize}

\subsection{Les blocs secondaires}
Les blocs secondaires sont des blocs qu'on trouve dans les règles de productions
\begin{itemize}
 \item \verb|INST -> BLOC|
 \item \verb|INST -> si E BLOC SIX|
 \item \verb|SIX -> sinon BLOC|
 \item \verb|INST -> tantque E BLOC |
\end{itemize}
Les variables déclarées dans de tels blocs doivent être éliminés dès la fin de leurs portées. C'est pourquoi à la fin du code de chaque bloc
on trouve un \verb|POP| de la taille des variables déclarées. Cette taille correspond à l'attribut \verb|taillev| qui se calcule de manière 
similaire au calcul des déplacements, mais qui est relative au bloc.

A noter que si un bloc secondaire contient le return de la fonction, le \verb|POP| vient après l'instruction du retour, il n'est pas
exécuté, et n'a \textit{a fortiori} aucun effet sur la bonne exécution du reste des intructions

\subsection{les conflits entre l'assembleur inline et Micro C}
\paragraph{Premier cas}
Soit le bout de code suivant \\%
\verb|if(condition){|\\%
\verb|int toto = 3 ;|\\%
\verb|asm{|\\%
\verb|SUBR IOut ;|\\%
\verb|}|\\%
\verb|}|\\%
La fin de ce bloc secondaire est accompagnée par un \verb|POP (0) 1| afin de libérer le registre occupé par la variable \verb|toto|.
Or l'instruction inline \verb|SUBR IOut ;| consomme cette variable et le \verb|POP| risque d'écraser le registre qui se trouve avant
ce bloc.
C'est au développeur de faire attention en chargeant toujours , dans la partie inline, les arguments qui vont être consommés.
\\%
\verb|if(condition){|\\%
\verb|int toto = 3 ;|\\%
\verb|asm{|\\%
 \verb|LOAD %toto ;|\\%
\verb|SUBR IOut ;|\\%
\verb|}|\\%
\verb|}|\\%
\paragraph{Second cas}
Soit le bout de code suivant \\%

\verb|int toto = 3 ;|\\%
\verb|asm{|\\%
\verb|LOADL 25 ;|\\%
\verb|}|\\%
\verb|}|\\%

Il est clair que  \verb|LOADL 25 ;| perturbe l'adressage.On a tenté de remédier à ce problème en calculant les déplacements 
dans l'inline (pour les \verb|LOADL| et \verb|PUSH|) mais il fallait décrémenter le déplacement de l'ASM dès l'appel d'une instruction
ou d'une fonction qui consomme des arguments, et l'incrémenter pour une fonction qui par exemple ne consomme aucun argument et produit 
un résultat (\verb|Iin|), ce qui requiert un travail énorme sur la grammaire de TAM.\\%
Ça revient toujours au développeur de faire gaffe...\\%


\paragraph{Troisième cas}
Soit la fonction suivante : \\%
\verb|int foo(int a, int b) {|\\%
\verb|asm{|\\%
\verb|RETURN (0) 0 ;|\\%
\verb|}|\\%
\verb|}|\\%
L'instruction de retour ne respecte pas la signature de la fonction et son type de retour, par conséquent perturbation de 
l'adressage.
Ce problème a été résolu (enfin...) en transmettant aux instructions de l'assembleur la taille des arguments et le type de 
retour.\\%
On compte quand même sur le développeur pour ne pas mettre d'instruction Return dans l'ASM du début , car tout simplement, 
ÇA N'A AUCUN SENS.\\%
\\%

D'autres conflits peuvent a priori surgir (il faut beaucoup plus de tests et de temps de réflexion pour arriver 
à couvrir la majorité des cas)  
\subsection{Du code après le retour}
la présence de code après une instruction de retour dans le bloc principal d'une fonction doit être interdite.
La méthode pour implémenter cette interdiction est de créer un attribut hérité de type booléen qui indique 
à une instruction si elle a été prcédée par une instruction de retour, et dans ce cas déclencher une erreur.\\%
Par contre, il faut permettre les retours dans les blocs secondaires du type \textit{si alors sinon} ou du \textit{tant que}, ce qui exige 
d'affiner encore plus les cas d'erreur.\\%
Pour le moment, on n'a pas encore implémenté cette solution.
\clearpage

\section{Tests}
\subsection{Objectifs et démarche des tests}


\subsection{Test arithmétiques}
\subsection{Test sur les pointeurs}
\subsection{Tests plus élaborés}
On a pu écrire des programmes assez complexes qui s'exécutent assez bien : 
\begin{itemize}
 \item Vérification qu'un entier est premmier ou non
 \item calcul des premiers inférieurs à un entier saisi au clavier
 \item calcul des n premiers termes de la suite de Fibonacci 
 \item Tri d'un tableau
 \item calcul de la valeur maximale d'un tableau dont les éléments sont saisis au clavier
\end{itemize}
Vu que ces tests touchent à plusieurs concepts traités dans ce compilateur, ils nous ont permis d'avoir l'assurance que
le compilateur implémenté serait  globalement correct (on ne peut jamais être sûr, SOS Marc Pantel pour la preuve de correction)

\clearpage

\section{Conclusion}
 On laisse la conclusion par la fin du projet.
\end{document}
